#include <iostream>
#include <string>
using namespace std;
int dp[2005][2005] = {};    // dp[i][j] 代表s1的前i个字符和s2的前j个字符能得到的最长公共子序列的长度
int tag[2005][2005] = {};   // 1左上方，2上方，3左方
string LCS(string s1, string s2) {
    int n = s1.length(), m = s2.length();
    for (int i = 0; i <= m; i++) dp[0][i] = 0;
    for (int i = 0; i <= n; i++) dp[i][0] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (s1[i - 1] == s2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
                tag[i][j] = 1;
            } else if (dp[i - 1][j] > dp[i][j - 1]) {
                dp[i][j] = dp[i - 1][j];
                tag[i][j] = 2;
            } else {
                dp[i][j] = dp[i][j - 1];
                tag[i][j] = 3;
            }
        }
    }
    if(dp[n][m] == 0) return "-1";
    string ans = "";
    int i = n, j = m;
    while (i>=1 && j>=1) {
        if (tag[i][j] == 2) {
            i--;
        } else if (tag[i][j] == 3) {
            j--;
        } else {
            ans = s1[i - 1] + ans;
            i--, j--;
        }
    }
    return ans;
}

int main() {
    return 0;
}